The past few years have witnessed a growing interest from the cryptographic community in computational algebra methods, in particular Gr\"obner basis algorithms \cite{Buchberger65,DBLP:journals/jsc/Buchberger06a}.
This was motivated by the proposal of algebraic attacks against stream ciphers~\cite{courtois-meier-euro03} and block ciphers~\cite{courtois-pieprzyk:asiacrypt02,DBLP:conf/cisc/FaugereP09,DBLP:conf/fse/AlbrechtC09,ACTFP10}, as well as
by the proposal of several public-key schemes based on systems of multivariate polynomial equations (e.g.,~\cite{patarin-euro96}), and the corresponding cryptanalysis using the
$F_5$ algorithm~\cite{faugere-joux-crypto03,DBLP:conf/crypto/FaugereP06,DBLP:conf/crypto/FaugereLP08,DBLP:conf/pkc/BouillaguetFFP11}.  One particular algorithm has received considerable attention from the cryptographic community: the XL algorithm \cite{courtois-klimov-patarin-shamir:eurocrypt2000} 
(and its several variants, e.g.,~\cite{courtois-patarin:ct-rsa03,courtois-pieprzyk:asiacrypt02,Courtois2004}) was originally proposed by cryptographers to tackle problems arising specifically from cryptology. Although not strictly a Gr\"obner basis algorithm, it used a similar idea to the one proposed by Lazard~\cite{lazard-eurocal83}: it constructs the Macaulay matrix up to some large degree $D$ and reduces it to obtain the solution of the system. The algorithm was shown to work only under particular conditions~\cite{diem-asia04}, while other flaws were also shown in other high-profile variants~\cite{Cid2005a,DBLP:conf/fse/LimK07}.
Eventually, it was shown that the XL algorithm could be described essentially as a redundant (and less efficient) variant of the $F_4$ algorithm \cite{DBLP:conf/asiacrypt/ArsFIKS04}. That is, one can simulate the XL algorithm using a variant of the $F_4$ algorithm.

Despite of these results, because of its simplicity the XL algorithm continues to attract the attention of researchers working in cryptography~\cite{mxl,thomae-wolf:eprint2010}. In this paper we investigate a prominent recent addition to the XL family, namely the MutantXL algorithms~\cite{mxl,mxl2,mxl3,mxl4}. The concept of Mutants was first introduced in \cite{mxl}, giving rise to a family of algorithms and techniques \cite{mxl2,mxl3,mxl4}, which showed to be particularly efficient against the MQQ multivariate cryptosystem \cite{mohamed-werner-ding-buchmann:cans09}.  Unlike the XL algorithm, some of the Mutant algorithms (e.g.,~ $\textrm{MXL}_3$~\cite{mxl3}) do in fact explicitly compute the Gr\"obner basis of the corresponding ideal, assuming it is zero-dimensional.
Because of the remarkable experimental results reported in~\cite{mxl3}, a natural question arises: what is behind such a performance? Is it due to changes in the algorithm, implementation tricks, tuning towards particular problems, or perhaps a fundamentally novel algorithmic idea?

In the MutantXL literature \cite{mxl,mxl2,mxl3,mxl4} the observed performance gains are attributed to algorithmic advances. Hence, in order to compare the MutantXL family of algorithms to standard techniques in computational commutative algebra, we need to describe both in common terms. This will allow us to answer the question, whether  mutants are a new concept or whether they can be described based on well-known computational algebra concepts. Likewise, are the new {\it mutant strategies} general enough, so that they can potentially be incorporated to existent Gr\"obner basis algorithms?

There has been so far no in-depth study of the mathematical properties of mutants and related strategies, and how they are connected to other Gr\"obner basis algorithms. Because of this, there is a considerable gap between the symbolic computation and the cryptographic communities. Both investigate efficient algorithms for solving polynomial systems but results seem incommensurable in terms of strategy.

In this work, we undertake the task to bridge this gap. In particular, we compare the MXL family with two variants of the $F_4$ algorithm \cite{F4}: first, the so-called simplified $F_4$ which does not use Buchberger's criteria to avoid useless reductions to zero and second, the full $F_4$ as specified in \cite{F4}. Considering these algorithms, we show that the Mutant strategy can be understood as essentially equivalent to the Normal Selection strategy as used in Gr\"obner basis algorithms, such as $F_4$. Based on previous results, which showed the relation between the XL algorithm and $F_4$ \cite{DBLP:conf/asiacrypt/ArsFIKS04}, we conclude that MXL can too be described as a redundant variant of $F_4$. Furthermore, we also study the ``partial enlargement'' strategy proposed in \cite{mxl2} and demonstrate that it corresponds to selecting a subset of S-polynomials in Gr\"obner basis algorithms. As a result, we conclude that MXL$_2$ can also be described as a variant of $F_4$, although a variant that diverges from known approaches about how to select the number of S-polynomials in each iteration.  Finally, we consider the new termination criterion proposed in \cite{mxl3} and demonstrate that it does not lead to a lower degree of termination than using Buchberger's criteria to remove useless pairs in a Gröbner basis algorithm. As a result, we reach the conclusion that MXL$_3$ can  be reduced to a redundant variant of the full $F_4$ algorithm.

Our work is in the tradition of previous papers comparing different approaches for polynomial system solving \cite{Mandache-phd,
Mandache-tc,Mandache1994}. We stress, however, that the equivalence of algorithms presented in this work is {\em constructive}, i.e., we show that the Mutant family of algorithms can be simulated using redundant variants of the $F_4$ algorithm.

The remaining of this work is organised as follows.  In Section~\ref{sec:xl} we recall the well-known XL algorithm, and re-state the result showing the relation between XL and $F_4$.  In Section~\ref{sec:gb} we review well-known statements from commutative algebra. For the sake of exposition, we place particular emphasis on the concept of
S-polynomials and the central role they play in Gr\"obner bases computations. In particular, we show that in XL-style algorithms any multiplication of polynomials by monomials except for those giving rise to S-polynomials is redundant. In Section~\ref{sec:mutants} we review the definition of Mutants, and present our pseudocode for the MXL$_3$ algorithm. In Section~\ref{sec:relation} we state and prove our main result, namely that the Mutant strategy is a redundant variant of the Normal Selection strategy. We also treat partial enlargement and the termination condition of MXL$_3$ in Section~\ref{sec:relation}. We conclude in Section~\ref{sec:conclusion}, where we include a brief discussion on what we view as the limitations of using running times as the {\it sole} basis for comparison between Gr\"obner basis {\it algorithms}.
